package com.buddy.summary.code.algorithm;

public class Algorithm_03 {

    //更相减损术与移位相结合 时间复杂度O(log(max(a,b)))
    private static int gcd(int a, int b) {
        if (a == b)
            return a;
        if ((a & 1) == 0 && (b & 1) == 0) {
            //如果a、b都是偶数
            return gcd(a >> 1, b >> 1) << 1;
        } else if ((a & 1) == 0 && (b & 1) != 0) {
            //如果a是偶数，b是奇数
            return gcd(a >> 1, b);
        } else if ((a & 1) != 0 && (b & 1) == 0) {
            return gcd(a, b >> 1);
        } else {
            //如果a,b都是奇数
            int big = a > b ? a : b;
            int small = a < b ? a : b;
            return gcd(big-small,small);
        }
    }

    public static void main(String[] args) {
        System.out.println(gcd(25,5));
        System.out.println(gcd(100,80));
        System.out.println(gcd(27,14));
        System.out.println(gcd(100000,800000));
    }
}
